package double_pointer;

import java.util.Arrays;

class TreeNode1 {
    int val;
    TreeNode1 left;
    TreeNode1 right;
    TreeNode1() {

    }
    TreeNode1(int val) {
        this.val = val;
    }
    TreeNode1(int val, TreeNode1 left, TreeNode1 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

//判断两棵树是否相同
public class isSameTree {
    public boolean isSameTree(TreeNode1 p, TreeNode1 q) {
    //如果两个都是空
    if(p == null && q == null) {
        return true;
    }
    //一边是空，一边不是空
    if(p == null && q != null || q == null && p != null) {
        return false;
    }
    //走到这里两边都不为空了，那么就判断值是否相等
    if(p.val != q.val) {
        return false;
    }
    //走到这里不为空值也相等，去判断左树和右树
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }



    //有效三角形的个数！！！

    // 判断三个数是否能组成三角形，只需要判断两个较小的数字之和能否大于最大数就可以
    // 先给数字排序，再根据单调性解题
    public int triangleNumber(int[] nums) {
        // 排序
        Arrays.sort(nums);
        //利用双指针解决问题
        int ret = 0;
        int n = nums.length;
        // 固定住一个最大值
        for (int i = n - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;
            // 需要保证 left < right
            while (left < right) {
                // 1. 大于最大值
                if (nums[left] + nums[right] > nums[i]) {
                    ret += right - left;
                    right--;
                } else { // 2. 小于最大值的情况
                    left++;
                }
            }
        }
        return ret;
    }

}
